package Year21_Month11.day1109;

public class Soultion {
    public static int fib(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        int pre = 1;
        int cur = 1;
        int key = 0;
        for(int i = 3;i <= n;i++){
            key = pre + cur;
            pre = cur;
            cur = key;
        }

        return key % 1000000007;
    }

    public static void main(String[] args) {
        System.out.println(fib(45));
    }
}
